package leetcode.graph.dfs.p785;
/**
 * 
 * @Title: Solution.java 
 * @Package leetcode.graph.p785 
 * @Description: 785. 判断二分图
 * @author CandyWall   
 * @date 2021年1月16日 上午10:51:02 
 * @version V1.0
 */
class Solution {
    private int[] colors;
    private int[][] graph;
    public boolean isBipartite(int[][] graph) {
        this.graph = graph;
        colors = new int[graph.length];
        for(int i = 0; i < graph.length; i++) {
            colors[i] = -1;
        }
        for(int v = 0; v < graph.length; v++) {
            if(colors[v] == -1) {
                if(!dfs(v, 0)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean dfs(int v, int color) {
        colors[v] = color;
        for(int w : graph[v]) {
            if(colors[w] == -1) {
                if(!dfs(w, 1 - color)) {
                    return false;
                }
            }
            else if(colors[w] == colors[v]) {
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isBipartite(new int[][]{{1, 3}, {0, 2}, {1, 3}, {0, 2}}));
        System.out.println(solution.isBipartite(new int[][]{{1,2,3}, {0, 2}, {0, 1, 3}, {0, 2}}));
    }
}